package org.dftproject.genesis.ui.figures.dualtree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.dftproject.genesis.ui.pages.pedigree.tree.OneToManyConnection;
import org.eclipse.draw2d.AbstractLayout;
import org.eclipse.draw2d.IFigure;
import org.eclipse.draw2d.geometry.Dimension;
import org.eclipse.draw2d.geometry.Point;
import org.eclipse.draw2d.geometry.Rectangle;

/**
 * Implements the Improved Walker's algorithm, as given in:
 * 
 * <pre>
 * @misc{ buchheim02improving,
 *  author = &quot;C. Buchheim and M. unger and S. Leipert&quot;,
 *  title = &quot;Improving Walker's algorithm to run in linear time&quot;,
 *  text = &quot;C. Buchheim, M. J unger, and S. Leipert. Improving Walker's algorithm to
 *  run in linear time. In Proc. Graph Drawing (GD), 2002.&quot;,
 *  year = &quot;2002&quot;,
 *  url = &quot;citeseer.ist.psu.edu/buchheim02improving.html&quot; }
 * </pre>
 */
public class ImprovedWalkersLayout extends AbstractLayout {

	private int verticalSpacing = 10;
	private int horizontalSpacing = 40;
	
	private DualTreeFigure dualTree;
	
	private final List<Integer> widths = new ArrayList<Integer>();
	
	private final Map<IFigure, Rectangle> boundsByFigure = new HashMap<IFigure, Rectangle>();

	private final Map<IFigure, Metadata> metadataByNode = new HashMap<IFigure, Metadata>();

	private IFigure defaultAncestor;
	
	public ImprovedWalkersLayout() {
	}
	
	public ImprovedWalkersLayout(int horizontalSpacing, int verticalSpacing) {
		this.horizontalSpacing = horizontalSpacing;
		this.verticalSpacing = verticalSpacing;
	}

	@Override
	protected Dimension calculatePreferredSize(IFigure container, int wHint, int hHint) {
		if (!(container instanceof DualTreeFigure))
			return new Dimension();
		dualTree = (DualTreeFigure) container;
		
		@SuppressWarnings("unchecked")
		List<IFigure> children = container.getChildren();
		if (!children.isEmpty() && children.get(0) instanceof IFigure) {
			IFigure root = children.get(0);
			computeTreeLayout(root);
			return getPreferredSize();
		}

		return new Dimension();
	}

	protected Dimension getPreferredSize() {
		Rectangle bounds = new Rectangle();
		for (Rectangle childBounds : boundsByFigure.values())
			bounds.union(childBounds);
		return bounds.getSize();
	}

	protected Point getUntranslatedOrigin() {
		Point origin = null;
		for (Rectangle childBounds : boundsByFigure.values()) {
			if (origin == null)
				origin = childBounds.getLocation();
			else {
				origin.x = Math.min(origin.x, childBounds.x);
				origin.y = Math.min(origin.y, childBounds.y);
			}
		}
		return origin;
	}

	public void layout(IFigure container) {
		if (!(container instanceof DualTreeFigure))
			return;
		dualTree = (DualTreeFigure) container;
		
		@SuppressWarnings("unchecked")
		List<IFigure> children = container.getChildren();
		if (children.isEmpty())
			return;
		
		if (children.get(0) instanceof IFigure) {
			IFigure root = children.get(0);
			treeLayout(container, root);
		}
		
		for (IFigure child : children) {
			if (child instanceof OneToManyConnection)
				((OneToManyConnection) child).layout();
		}
	}

	protected Metadata getMetadata(IFigure node) {
		Metadata metadata = metadataByNode.get(node);
		if (metadata == null) {
			metadata = new Metadata(node);
			metadataByNode.put(node, metadata);
		}
		return metadata;
	}

	protected void computeTreeLayout(IFigure v) {
		widths.clear();
		boundsByFigure.clear();
		metadataByNode.clear();
		defaultAncestor = null;

		firstWalk(v, 0);
		secondWalk(v, -getMetadata(v).prelim, 0, 0);
	}
	
	protected void treeLayout(IFigure container, IFigure v) {
		Point origin = container.getClientArea().getLocation().getTranslated(getUntranslatedOrigin().getNegated());
		thirdWalk(v, origin.x, origin.y);
	}

	protected void firstWalk(IFigure v, int depth) {
		if (widths.size() > depth)
			widths.set(depth, Math.max(widths.get(depth), v.getPreferredSize().width));
		else
			widths.add(v.getPreferredSize().width);
		
		if (isLeaf(v)) {
			IFigure s = getLeftSibling(v);
			if (s != null)
				getMetadata(v).prelim = getMetadata(s).prelim + s.getPreferredSize().height + verticalSpacing;
		} else {
			defaultAncestor = getLeftmostChild(v);

			for (IFigure w : dualTree.getAncestors(v)) {
				if (w != null) {
					firstWalk(w, depth + 1);
					apportion(w);
				}
			}

			executeShifts(v);

			IFigure first = getLeftmostChild(v);
			IFigure last = getRightmostChild(v);
			int midpoint = (getMetadata(first).prelim + first.getPreferredSize().height / 2 + getMetadata(last).prelim + last.getPreferredSize().height / 2 - v.getPreferredSize().height) / 2;

			IFigure w = getLeftSibling(v);
			if (w != null) {
				getMetadata(v).prelim = getMetadata(w).prelim + w.getPreferredSize().height + verticalSpacing;
				getMetadata(v).mod = getMetadata(v).prelim - midpoint;
			} else {
				getMetadata(v).prelim = midpoint;
			}
		}
	}
	
	protected IFigure getChild(IFigure v) {
		IFigure[] descendants = dualTree.getDescendants(v);
		if (descendants.length == 0 || descendants[0] == null)
			return null;
		return descendants[0];
	}

	protected boolean isLeaf(IFigure v) {
		for (IFigure w : dualTree.getAncestors(v)) {
			if (w != null)
				return false;
		}
		return true;
	}

	protected IFigure getLeftmostChild(IFigure v) {
		for (IFigure w : dualTree.getAncestors(v)) {
			if (w != null)
				return w;
		}
		return null;
	}

	protected IFigure getRightmostChild(IFigure v) {
		IFigure[] children = dualTree.getAncestors(v);
		for (int i = children.length - 1; i >= 0; i--) {
			if (children[i] != null)
				return children[i];
		}
		return null;
	}

	protected IFigure getLeftSibling(IFigure w) {
		IFigure v = getChild(w);;
		if (v == null)
			return null;
		IFigure prev = null;
		for (IFigure s : dualTree.getAncestors(v)) {
			if (s == w)
				return prev;
			if (s != null)
				prev = s;
		}

		return null;
	}

	protected void apportion(IFigure v) {
		IFigure w = getLeftSibling(v);
		if (w != null) {
			IFigure vip = v;
			IFigure vop = v;
			IFigure vin = w;
			IFigure von = getLeftmostSibling(vip);
			int sip = getMetadata(vip).mod;
			int sop = getMetadata(vop).mod;
			int sin = getMetadata(vin).mod;
			int son = getMetadata(von).mod;
			while (nextRight(vin) != null && nextLeft(vip) != null) {
				vin = nextRight(vin);
				vip = nextLeft(vip);
				von = nextLeft(von);
				vop = nextRight(vop);
				getMetadata(vop).ancestor = v;
				int shift = (getMetadata(vin).prelim + sin) - (getMetadata(vip).prelim + sip) + vin.getPreferredSize().height + verticalSpacing;
				if (shift > 0) {
					moveSubtree(ancestor(vin, v), v, shift);
					sip += shift;
					sop += shift;
				}
				sin += getMetadata(vin).mod;
				sip += getMetadata(vip).mod;
				son += getMetadata(von).mod;
				sop += getMetadata(vop).mod;
			}

			if (nextRight(vin) != null && nextRight(vop) == null) {
				getMetadata(vop).thread = nextRight(vin);
				getMetadata(vop).mod += sin - sop;
			}

			if (nextLeft(vip) != null && nextLeft(von) == null) {
				getMetadata(von).thread = nextLeft(vip);
				getMetadata(von).mod += sip - son;
				defaultAncestor = v;
			}
		}
	}

	protected IFigure getLeftmostSibling(IFigure w) {
		IFigure v = getChild(w);;
		for (IFigure s : dualTree.getAncestors(v)) {
			if (s == w)
				return null;
			if (s != null)
				return s;
		}

		return null;
	}

	protected IFigure nextLeft(IFigure v) {
		for (IFigure w : dualTree.getAncestors(v)) {
			if (w != null)
				return w;
		}
		return getMetadata(v).thread;
	}

	protected IFigure nextRight(IFigure v) {
		IFigure[] children = dualTree.getAncestors(v);
		for (int i = children.length - 1; i >= 0; i--) {
			if (children[i] != null)
				return children[i];
		}
		return getMetadata(v).thread;
	}

	protected void moveSubtree(IFigure wn, IFigure wp, int shift) {
		int subtrees = getSubtreeIndex(wp) - getSubtreeIndex(wn) - 1;
		if (subtrees <= 0)
			subtrees = 1;
		getMetadata(wp).change -= shift / subtrees;
		getMetadata(wp).shift += shift;
		getMetadata(wn).change += shift / subtrees;
		getMetadata(wp).prelim += shift;
		getMetadata(wp).mod += shift;
	}

	protected int getSubtreeIndex(IFigure w) {
		IFigure v = getChild(w);;
		if (v == null)
			return 0;
		IFigure[] children = dualTree.getAncestors(v);
		for (int i = 0; i < children.length; i++) {
			if (children[i] == w)
				return i;
		}
		return -1;
	}

	protected void executeShifts(IFigure v) {
		int shift = 0;
		int change = 0;

		IFigure[] children = dualTree.getAncestors(v);
		for (int i = children.length - 1; i >= 0; i--) {
			if (children[i] != null) {
				getMetadata(children[i]).prelim += shift;
				getMetadata(children[i]).mod += shift;
				change += getMetadata(children[i]).change;
				shift += getMetadata(children[i]).shift + change;
			}
		}
	}

	protected IFigure ancestor(IFigure vin, IFigure v) {
		IFigure ancestor = getMetadata(vin).ancestor;
		if (ancestor != null && getChild(ancestor) == getChild(v) && ancestor != v)
			return ancestor;
		else
			return defaultAncestor;
	}

	protected void secondWalk(IFigure v, int m, int depth, int x) {
		Dimension preferredSize = v.getPreferredSize();
		boundsByFigure.put(v, new Rectangle(x, getMetadata(v).prelim + m, preferredSize.width, preferredSize.height));
		for (IFigure w : dualTree.getAncestors(v)) {
			if (w != null)
				secondWalk(w, m + getMetadata(v).mod, depth + 1, x + widths.get(depth) + horizontalSpacing);
		}
	}

	/**
	 * Walks the tree moving nodes so that the smallest bounding box is located
	 * at the origin.
	 * @param v the root node
	 * @param dx translation distance along the x axis
	 * @param dy translation distance along the y axis
	 */
	protected void thirdWalk(IFigure v, int dx, int dy) {
		Rectangle bounds = boundsByFigure.get(v);
		if (bounds != null)
			v.setBounds(bounds.getTranslated(dx, dy));
		for (IFigure w : dualTree.getAncestors(v)) {
			if (w != null)
				thirdWalk(w, dx, dy);
		}
	}

	protected class Metadata {

		public int prelim;
		public int mod;
		public IFigure ancestor;
		public IFigure thread;
		public int change;
		public int shift;

		public Metadata(IFigure node) {
			ancestor = node;
		}

	}

	public int getVerticalSpacing() {
		return verticalSpacing;
	}

	public int getHorizontalSpacing() {
		return horizontalSpacing;
	}

	public void setVerticalSpacing(int verticalSpacing) {
		this.verticalSpacing = verticalSpacing;
	}

	public void setHorizontalSpacing(int horizontalSpacing) {
		this.horizontalSpacing = horizontalSpacing;
	}

}
